package erfgame.core.world.terrain;

import java.awt.Dimension;
import java.awt.Point;
import java.awt.Rectangle;
import java.io.DataInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.logging.Level;
import java.util.logging.Logger;
import java.util.zip.GZIPInputStream;
import java.util.zip.GZIPOutputStream;


import erfgame.core.Dimensions3D;
import erfgame.core.Pair;
import erfgame.core.Point3D;
import erfgame.core.Point3DAndRotation;
import erfgame.core.Rectangle3D;
import erfgame.core.Rotation;
import erfgame.core.dao.ObjectDAO;
import erfgame.core.entity.Entity;
import erfgame.core.entity.Physical;
import erfgame.core.graphics.renderer.RendererContext;
import erfgame.core.graphics.renderer.chain.RendererChain;
import erfgame.core.memory.Pointer;
import erfgame.core.util.ArrayUtils;
import erfgame.core.util.ColorUtils;
import erfgame.core.util.RangeUtils;
import erfgame.core.world.World;
import erfgame.core.world.WorldDAOManager;
import erfgame.core.world.terrain.insertion.SurfaceRendererInsertion;
import erfgame.core.world.terrain.rotated.RotatedWorld;
import erfgame.core.world.terrain.update.BlockSurfaceImageUpdater;
import erfgame.core.world.terrain.update.TerrainBlockUpdateResult;
import erfgame.core.world.terrain.update.TerrainBlockUpdater;

public final class TerrainUtils {
	
	private static final Logger log = Logger.getLogger(TerrainUtils.class.getName());
	
	private static final int MAX_PATHS = 128;
	// NOTE 
	// by setting this to the maximum sample length of the colour function 
	// we avoid the need for any bounds checking, it's also massive overkill
	//ColorUtils.MAX_DIFF
	
	private static final int SAMPLE_BUFFER = ColorUtils.MAX_DIFF+1;
	
	private static final int SKY_HEIGHT = Byte.MAX_VALUE;
	
	public static final void overwriteTerrain(
			World world, 
			int worldX,
			int worldY, 
			int worldZ,
			Rotation priorityRotation,
			TerrainUpdateGroup terrainUpdate, 
			WorldDAOManager worldDAOManager,
			BlockSurfaceImageFactoryManager bsiFactoryManager
	) {
		ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO = worldDAOManager.getBlockTerrainDAO(world);
		ObjectDAO<Point3DAndRotation, BlockSurfaceImages> bsiDAO = worldDAOManager.getBlockSurfaceImagesDAO(world);
		BlockSurfaceImageFactory bsiFactory = bsiFactoryManager.getFactory(world);
		ObjectDAO<Point, int[][][]> surfacesDAO = worldDAOManager.getSurfacesDAO(world);
		ObjectDAO<Point, BlockGridTiles> gridTilesDAO = worldDAOManager.getGridTilesDAO(world);
		
		List<Pair<Point3D, TerrainUpdate>> updates = terrainUpdate.getTerrainUpdates();
		for( int i=updates.size(); i>0; ) {
			i--;
			Pair<Point3D, TerrainUpdate> pair = updates.get( i );
			Point3D position = pair.getFirst();
			TerrainUpdate update = pair.getSecond();
			
			overwriteTerrain(
					world, 
					worldX + position.x, 
					worldY + position.y, 
					worldZ + position.z, 
					priorityRotation,
					update, 
					terrainDAO, 
					bsiDAO, 
					bsiFactory, 
					surfacesDAO, 
					gridTilesDAO
			);			
		}
	}

	public static final void overwriteTerrain(
			World world, 
			int worldX,
			int worldY, 
			int worldZ,
			Rotation priorityRotation,
			TerrainUpdate terrainUpdate, 
			WorldDAOManager worldDAOManager,
			BlockSurfaceImageFactoryManager bsiFactoryManager
	) {
		ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO = worldDAOManager.getBlockTerrainDAO(world);
		ObjectDAO<Point3DAndRotation, BlockSurfaceImages> bsiDAO = worldDAOManager.getBlockSurfaceImagesDAO(world);
		BlockSurfaceImageFactory bsiFactory = bsiFactoryManager.getFactory(world);
		ObjectDAO<Point, int[][][]> surfacesDAO = worldDAOManager.getSurfacesDAO(world);
		ObjectDAO<Point, BlockGridTiles> gridTilesDAO = worldDAOManager.getGridTilesDAO(world);
		overwriteTerrain(
				world, 
				worldX, 
				worldY, 
				worldZ, 
				priorityRotation,
				terrainUpdate, 
				terrainDAO, 
				bsiDAO, 
				bsiFactory, 
				surfacesDAO, 
				gridTilesDAO
		);
	}
	
	public static final void overwriteTerrain( 
			World world,
			int worldX, int worldY, int worldZ, 
			Rotation priorityRotation,
			TerrainUpdate terrainUpdate,
			ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO, 
			ObjectDAO<Point3DAndRotation, BlockSurfaceImages> bsiDAO, 
			BlockSurfaceImageFactory bsiFactory, 
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point, BlockGridTiles> gridTilesDAO
	){

		int terrainWidth = terrainUpdate.getWidth();
		int terrainHeight = terrainUpdate.getHeight();
		int terrainDepth = terrainUpdate.getDepth();

		TerrainBlockUpdater terrainUpdater = new TerrainBlockUpdater( SAMPLE_BUFFER*2 );
		TerrainBlockUpdateResult terrainUpdateResult = terrainUpdater.updateTerrainBlocks(
				world, 
				terrainUpdate, 
				worldX, 
				worldY, 
				worldZ, 
				terrainDAO, 
				surfacesDAO
		);

		// TODO : calculate the diffs for the grid + surfaces
		log.log( Level.INFO, "updating surfaces" );
		updateSurfaces(
				worldX, worldY, worldZ,
				terrainUpdate,
				terrainUpdateResult,
				world, 
				surfacesDAO
		);
		
		terrainUpdater.loadShadowBlocks(
				world,
				terrainUpdate, 
				terrainUpdateResult, 
				worldX, 
				worldY, 
				worldZ, 
				terrainDAO
		);
		
		
		log.log( Level.INFO, "creating images" );
		BlockSurfaceImageUpdater imageUpdater = new BlockSurfaceImageUpdater( terrainDAO, surfacesDAO, SAMPLE_BUFFER );
		imageUpdater.updateBlockSurfaceImages(
				world, 
				terrainUpdate, 
				worldX, 
				worldY, 
				worldZ, 
				priorityRotation, 
				terrainUpdateResult, 
				bsiDAO, 
				bsiFactory
		);
		// TODO : thread non-priority rotations		

		int pathDiagonal = world.getGridDiagonal() / 2;
		int maxpx = (world.getWorldWidth()-1) / pathDiagonal;
		int maxpy = (world.getWorldHeight()-1) / pathDiagonal;
		int startpx = worldX / pathDiagonal;
		int startpy = worldY / pathDiagonal;
		if( worldX % pathDiagonal != 0 ) {
			startpx++;
		}
		if( worldY % pathDiagonal != 0 ) {
			startpy++;
		}
		int endpx = ( worldX + terrainWidth - 1 ) / pathDiagonal;
		int endpy = ( worldY + terrainHeight - 1 ) / pathDiagonal;
		
		int startepx;
		if( startpx <= 0 ) {
			startepx = 0;
			startpx = 0;
		} else {
			startepx = startpx-1;
		}
		int endepx;
		if( endpx >= maxpx ) {
			endpx = maxpx;
			endepx = maxpx;
		} else {
			endepx = endpx+1;
		}
		int startepy;
		if( startpy <= 0 ) {
			startepy = 0;
			startpy = 0;
		} else {
			startepy = startpy - 1;
		}
		int endepy;
		if( endpy >= maxpy ) {
			endepy = maxpy;
			endpy = maxpy;
		} else {
			endepy = endpy + 1;
		}
		
		log.log( Level.INFO, "setting paths ("+worldX+","+worldY+")("+(worldX+terrainWidth)+","+(worldY+terrainHeight)+") -> ("+startpx+","+startpy+")("+endpx+","+endpy+")" );		
		
		updateGridTiles(
				startpx, 
				startpy, 
				endpx, 
				endpy,
				startepx, 
				startepy, 
				endepx, 
				endepy,
				surfacesDAO, 
				gridTilesDAO, 
				world
		);
		
		log.log( Level.INFO, "updating non-priority angles" );
		Rotation[] rotations = Rotation.values();
		for( int i=rotations.length; i>0; ) {
			i--;
			Rotation rotation = rotations[i];
			if( rotation != priorityRotation ) {
				// TODO : thread? or assume all of this is already threaded?
				imageUpdater.updateBlockSurfaceImages(
						world, 
						terrainUpdate, 
						worldX, 
						worldY, 
						worldZ, 
						rotation, 
						terrainUpdateResult, 
						bsiDAO, 
						bsiFactory
				);
			}
		}
		terrainUpdateResult.free();
		log.log( Level.INFO, "done updating terrain" );
	}
	
	public static final int getSurfaceDepth( byte[][][] terrain, int x, int y ) {
		byte[] terrainXY = terrain[x][y];
		for( int z = 0; z<terrainXY.length; z++ ) {
			byte ttz = terrainXY[z];
			if( ttz != TerrainConstants.TERRAIN_TYPE_AIR ) {
				return z;
			}
		}
		return -1;
	}

	public static final void compress( OutputStream outs, byte[][][] terrain, int tw, int th, int td ) 
		throws IOException {
		// TODO : use a more appropriate compression algorithm
		GZIPOutputStream zip = new GZIPOutputStream( outs );
		for( int x=tw; x>0; ) {
			x--;
			byte[][] terrainX = terrain[x];
			for( int y=th; y>0; ) {
				y--;
				zip.write( terrainX[y], 0, td );
			}
		}
		zip.finish();
	}

	public static final byte[][][] uncompress( InputStream ins, byte[][][] into, int tw, int th, int td ) 
		throws IOException {
		// TODO : use a faster decompression algorithm
		DataInputStream zip = new DataInputStream( new GZIPInputStream( ins ) );
		for( int x=tw; x>0; ) {
			x--;
			byte[][] intoX = into[ x ];
			for( int y=th; y>0; ) {
				y--;
				zip.readFully( intoX[y], 0, td );
			}
		}
		return into;
	}
	
	public static final void moveEntity(
			World world,
			Entity entity, 
			Point3D newPosition,
			ObjectDAO<Point3D, BlockEntityPositions> entityPositionsDAO,
			ObjectDAO<Long, Entity> entityDAO,
			RendererContext context
	) {
		Physical physical = (Physical)entity;
		Point3D oldPosition = physical.getPosition();
		Dimensions3D dimensions = physical.getDimensions();
		int oldXstart = oldPosition.x - dimensions.width/2;
		int oldYstart = oldPosition.y - dimensions.height/2;
		int oldZstart = oldPosition.z - dimensions.depth;
		int oldXend = oldXstart + dimensions.width;
		int oldYend = oldYstart + dimensions.height;
		int oldZend = oldZstart + dimensions.depth;
		
		int oldBXstart = oldXstart >> world.getBlockWidthShift();
		int oldBYstart = oldYstart >> world.getBlockHeightShift();
		int oldBZstart = oldZstart / world.getBlockDepth();
		int oldBXend = oldXend >> world.getBlockWidthShift();
		int oldBYend = oldYend >> world.getBlockHeightShift();
		int oldBZend = oldZend / world.getBlockDepth();
		
		int newXstart = newPosition.x - dimensions.width/2;
		int newYstart = newPosition.y - dimensions.height/2;
		int newZstart = newPosition.z - dimensions.depth;
		int newXend = newXstart + dimensions.width;
		int newYend = newYstart + dimensions.height;
		int newZend = newZstart + dimensions.depth;

		int newBXstart = newXstart >> world.getBlockWidthShift();
		int newBYstart = newYstart >> world.getBlockHeightShift();
		int newBZstart = newZstart / world.getBlockDepth();
		int newBXend = newXend >> world.getBlockWidthShift();
		int newBYend = newYend >> world.getBlockHeightShift();
		int newBZend = newZend / world.getBlockDepth();
		
		for( int bx=oldBXstart; bx<=oldBXend; bx++ ) {
			boolean inNewX = newBXstart <= bx && newBXend >= bx;
			for( int by=oldBYstart; by<=oldBYend; by++ ) {
				boolean inNewY = newBYstart <= by && newBYend >= by;
				for( int bz=oldBZstart; bz<=oldBZend; bz++ ) {
					boolean inNewZ = newBZstart <= bz && newBZend >= bz;
					if( !inNewZ || !inNewY || !inNewX ) {
						// remove the entity
						Point3D key = new Point3D( bx, by, bz );
						BlockEntityPositions positions = entityPositionsDAO.retrieveObject(key);
						positions.getEntities().remove(entity);
						entityPositionsDAO.storeObject(key, positions);
					}
				}
			}
		}
		for( int bx=newBXstart; bx<=newBXend; bx++ ) {
			boolean inOldX = oldBXstart <= bx && oldBXend >= bx;
			for( int by=newBYstart; by<=newBYend; by++ ) {
				boolean inOldY = oldBYstart <= by && oldBYend >= by;
				for( int bz=newBZstart; bz<=newBZend; bz++ ) {
					boolean inOldZ = oldBZstart <= bz && oldBZend >= bz;
					if( !inOldX || !inOldY || !inOldZ ) {
						Point3D key = new Point3D( bx, by, bz );
						BlockEntityPositions positions = entityPositionsDAO.retrieveObject(key);
						positions.getEntities().add(entity);
						entityPositionsDAO.storeObject(key, positions);						
					}
				}
			}
		}
		physical.setPosition( newPosition );
		entityDAO.storeObject(entity.getId(), entity);
		if( context != null ) {
			context.considerEntity(entity);
		}
	}
	
	public static final void removeEntity(
			World world, 
			Entity entity, 
			ObjectDAO<Point3D, BlockEntityPositions> entityPositionsDAO, 
			ObjectDAO<Long, Entity> entityDAO,
			RendererContext context
	) {
		Physical physical = (Physical)entity;
		Point3D oldPosition = physical.getPosition();
		Dimensions3D dimensions = physical.getDimensions();
		int oldXstart = oldPosition.x - dimensions.width/2;
		int oldYstart = oldPosition.y - dimensions.height/2;
		int oldZstart = oldPosition.z - dimensions.depth;
		int oldXend = oldXstart + dimensions.width;
		int oldYend = oldYstart + dimensions.height;
		int oldZend = oldZstart + dimensions.depth;
		
		int oldBXstart = oldXstart >> world.getBlockWidthShift();
		int oldBYstart = oldYstart >> world.getBlockHeightShift();
		int oldBZstart = oldZstart / world.getBlockDepth();
		int oldBXend = oldXend >> world.getBlockWidthShift();
		int oldBYend = oldYend >> world.getBlockHeightShift();
		int oldBZend = oldZend / world.getBlockDepth();
		for( int bx=oldBXstart; bx<=oldBXend; bx++ ) {
			for( int by=oldBYstart; by<=oldBYend; by++ ) {
				for( int bz=oldBZstart; bz<=oldBZend; bz++ ) {
					// remove the entity
					Point3D key = new Point3D( bx, by, bz );
					BlockEntityPositions positions = entityPositionsDAO.retrieveObject(key);
					positions.getEntities().remove(entity);
					entityPositionsDAO.storeObject(key, positions);
				}
			}
		}
		entityDAO.removeObject(entity.getId());
		if( context != null ) {
			context.forgetEntity(entity);
		}
	}
	
	public static final void addEntity(
		World world,
		Entity entity, 
		ObjectDAO<Point3D, BlockEntityPositions> entityPositionsDAO, 
		ObjectDAO<Long, Entity> entityDAO,
		RendererContext context
	) {
		Physical physical = (Physical)entity;
		Point3D position = physical.getPosition();
		Dimensions3D dimensions = physical.getDimensions();
		
		entityDAO.storeObject(entity.getId(), entity);
		
		int newXstart = position.x - dimensions.width/2;
		int newYstart = position.y - dimensions.height/2;
		int newZstart = position.z - dimensions.depth;
		int newXend = newXstart + dimensions.width;
		int newYend = newYstart + dimensions.height;
		int newZend = newZstart + dimensions.depth;

		int newBXstart = newXstart >> world.getBlockWidthShift();
		int newBYstart = newYstart >> world.getBlockHeightShift();
		int newBZstart = newZstart / world.getBlockDepth();
		int newBXend = newXend >> world.getBlockWidthShift();
		int newBYend = newYend >> world.getBlockHeightShift();
		int newBZend = newZend / world.getBlockDepth();
		
		for( int bx=newBXstart; bx<=newBXend; bx++ ) {
			for( int by=newBYstart; by<=newBYend; by++ ) {
				for( int bz=newBZstart; bz<=newBZend; bz++ ) {
					Point3D key = new Point3D( bx, by, bz );
					BlockEntityPositions positions = entityPositionsDAO.retrieveObject(key);
					positions.getEntities().add(entity);
					entityPositionsDAO.storeObject(key, positions);						
				}
			}
		}
		if( context != null ) {
			context.considerEntity(entity);
		}
	}
	
	
	public static final SurfaceRendererInsertion createInsertion(
			RotatedWorld world, 
			Point3D key, 
			RendererChain renderer
	) {
		Rotation rotation = world.getRotation();
		Dimension dimension = renderer.getHead().getDimension();
		Point grabPoint = renderer.getHead().getGrabPoint();
		
		Entity entity = renderer.getHead().getEntity();
		Physical physical = (Physical)entity; 
		int entityDepth = renderer.getHead().getDepth(world.getRotation());
		Point3D position = physical.getPosition();
		
		int blockWorldX = key.x << world.getBlockWidthShift();
		int blockWorldY = key.y << world.getBlockHeightShift();
		
		// rotate
		Point blockMidPoint = world.getBlockMidPointTimes2();
		Point3D rotatedPosition = new Point3D();
		rotatedPosition.z = position.z;
		rotation.getOpposite().rotateInBox(
				position.x - blockWorldX, 
				position.y - blockWorldY, 
				blockMidPoint.x, 
				blockMidPoint.y, 
				rotatedPosition
		);
		
		
		int startX = rotatedPosition.x - grabPoint.x + blockWorldX;
//		int startY = rotatedPosition.y + blockWorldY;
		int startZ = rotatedPosition.z - grabPoint.y;

		int y = rotatedPosition.y;
		if( y >= 0 ) {
			// take off half the depth of the entity
			int depth = (world.getBlockHeight() - y - entityDepth)/2;
			
			Rectangle imageBounds = new Rectangle( 
					startX, 
					startZ, 
					dimension.width, 
					dimension.height 
			);
			return createInsertion( world, key, imageBounds, depth, y, renderer );
		} else {
			return null;
		}
	}
	
	public static final SurfaceRendererInsertion createInsertion( 
			RotatedWorld world, 
			Point3D key, 
			Rectangle imageBounds, 
			int depth, 
			int y,
			RendererChain renderer
	) {
		int headRoom = world.getBlockHeight() >> 1;
		int blockZ = key.z * world.getBlockDepth();
		int minY = BlockSurfaceImageFactory.getPixelY( y, imageBounds.y );
		int maxY = BlockSurfaceImageFactory.getPixelY( y, Math.min(imageBounds.height+imageBounds.y, blockZ+world.getBlockDepth()) );
		Rectangle adjustedImageBounds = new Rectangle(
				imageBounds.x, 
				minY, 
				imageBounds.width, 
				maxY - minY
		);
		Rectangle blockBounds = new Rectangle( 
				key.x << world.getBlockWidthShift(), 
				blockZ, 
				world.getBlockWidth(), 
				world.getBlockDepth() + headRoom
		);
		Rectangle intersection = adjustedImageBounds.intersection( blockBounds );
		SurfaceRendererInsertion insertion;

		if( intersection.width > 0 && intersection.height > 0 ) {
			int xoff = intersection.x - adjustedImageBounds.x;
			int yoff = intersection.y - adjustedImageBounds.y;
			
			// these aren't actually the screen coordinates, just the overlaps of the x and z 
			// coordinates
//			int x = intersection.x - blockBounds.x;
//			int z = intersection.y - blockBounds.y;
//			
//			int px = x;
//			int py = BlockSurfaceImageFactory.getPixelY( y, z );
			
			// reuse intersection
//			intersection.x = px;
//			intersection.y = py;
			
			intersection.x -= blockBounds.x;
			intersection.y -= blockBounds.y;

			int renderBoundsY = Math.max( intersection.y, BlockSurfaceImageFactory.getPixelY(y, 0));
			
			insertion = new SurfaceRendererInsertion(
					depth, 
					renderer, 
					xoff, 
					yoff, 
					intersection,
					renderBoundsY,
					key
			);
		} else {
			insertion = null;
		}
		return insertion;
	}
	
	public static final int[][][] deriveTerrainSummary(short[][][] terrain, int[][][] surfaces, int width, int height) {
		int[] temp = new int[MAX_PATHS];
		for( int x=width; x>0; ) {
			x--;
			short[][] terrainX = terrain[x];
			int[][] surfacesX = surfaces[x];
			for( int y=height; y>0; ) {
				y--;
				short[] terrainXY = terrainX[y];
				int size = deriveTerrainSummary(terrainXY, temp);
				int[] surfacesXY = new int[ size ];
				System.arraycopy( temp, temp.length - size, surfacesXY, 0, size );
				surfacesX[y] = surfacesXY;
			}
		}
		return surfaces;
	}
	
	public static final int deriveTerrainSummary(short[] terrain, int[] into ) {
		int index = into.length;
		short terrainType = TerrainUpdate.FLAG_OVERWRITE_IF_AIR;
		int terrainTypeCount = 0;
		for( int tz=terrain.length; tz>0; ) {
			tz--;
			short t = terrain[tz];
			if( t != terrainType ) {
				if( terrainTypeCount > 0 ) { 
					index--;
					into[index] = terrainTypeCount;
				}
				terrainType = t;
				terrainTypeCount = 1;
			} else {
				terrainTypeCount++;
			}
		}
		index--;
		into[index] = terrainTypeCount;
		return into.length - index;
	}
	
	public static final void deriveSurfaces(int bx, int by, int startx, int starty, int endx, int endy, int[][][] surfaces, byte[][][] terrain, ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO, World world ) {
		for( int bz=0; bz<world.getBlocksZ(); bz++ ) {
			Pointer<byte[][][]> t = terrainDAO.retrieveObject(new Point3D(bx, by, bz));
			updateSurfaces(bx, by, bz, startx, starty, endx, endy, surfaces, t.getValue(), world);
			t.free();
		}
	}

	public static final void updateSurfaces(
			int worldX, 
			int worldY, 
			int worldZ, 
			TerrainUpdate terrainUpdate,
			TerrainBlockUpdateResult terrainUpdateResult,
			World world, 
			ObjectDAO<Point, int[][][]> surfacesDAO
	) {
		int maxShadowDepth = world.getMaxShadowDepth();
		int terrainWidth = terrainUpdate.getWidth();
		int terrainHeight = terrainUpdate.getHeight(); 
		int terrainDepth = terrainUpdate.getDepth();
		int[][][] terrainSummary = terrainUpdate.getSummary();
		short[][][] terrain = terrainUpdate.getTerrain();

		int[][][][][] allSurfaces = terrainUpdateResult.getSurfaces();
		Rectangle3D sampleBounds = terrainUpdateResult.getSampleBounds();
		
		
		int[] temp = new int[ world.getWorldDepth() ];
		// assume that the coords are normalised
		// assume is always more efficient to reuse blocks
		int startBlockX = worldX >> world.getBlockWidthShift();
		int startBlockY = worldY >> world.getBlockHeightShift();

		int endBlockX = (worldX+terrainWidth-1) >> world.getBlockWidthShift();
		int endBlockY = (worldY+terrainHeight-1) >> world.getBlockHeightShift();

		// use the surface summary to make this faster

//		System.out.println("("+worldX+","+worldY+","+worldZ+")" );
//		System.out.println("<"+world.getBlockWidth()+"x"+world.getBlockHeight()+"x"+world.getBlockDepth()+">");
//		System.out.println("["+startBlockX+","+startBlockY+","+startBlockZ+"]->["+endBlockX+","+endBlockY+","+endBlockZ+"]");
		
		int checkedEndBlockX = Math.min( endBlockX, world.getBlocksX()-1 );
		int checkedEndBlockY = Math.min( endBlockY, world.getBlocksY()-1 );
		
		int checkedStartBlockX = Math.max( startBlockX, 0 );
		int checkedStartBlockY = Math.max( startBlockY, 0 );

		int endz = Math.min( worldZ + terrainDepth - 1, world.getWorldDepth()-1 );
		int maxBottomZ = -1;
		int minBottomZ = -1;
		int[] outMaxZ = new int[1];

		int startz = worldZ;
		
		int xoff = checkedStartBlockX - sampleBounds.minX;
		int yoff = checkedStartBlockY - sampleBounds.minY;

		for( int bx=checkedStartBlockX; bx<=checkedEndBlockX; bx++ ) {
			
			int startSummaryX;  
			int startX;
			if( bx == startBlockX ) {
				startSummaryX = 0;
				startX = worldX & world.getBlockWidthMask();
			} else {
				startSummaryX = (bx - checkedStartBlockX) * world.getBlockWidth() - (worldX % world.getBlockWidth()); 
				startX = 0;
			}
			int endX;
			if( bx == endBlockX ) {
				endX = (worldX + terrainWidth - 1) & world.getBlockWidthMask();
			} else {
				endX = world.getBlockWidth() - 1;
			}
			for( int by=checkedStartBlockY; by<=checkedEndBlockY; by++ ) {
				int startY;
				int startSummaryY;
				if( by == startBlockY ) {
					startSummaryY = 0;
					startY = worldY & world.getBlockHeightMask();
				} else {
					startSummaryY = (by - checkedStartBlockY) * world.getBlockHeight() - (worldY & world.getBlockHeightMask()); 
					startY = 0;
				}


				int endY;
				if( by == endBlockY ) {
					endY = ( worldY + terrainHeight - 1) & world.getBlockHeightMask();
				} else {
					endY = world.getBlockHeight()-1;
				}
				// get the surfaces
				int[][][] surfaces = allSurfaces[bx-startBlockX+xoff][by-startBlockY+yoff];

				int summaryX = startSummaryX;
				for( int x=startX; x<=endX; x++ ) {
					int[][] surfacesX = surfaces[x];
					int[][] terrainSummaryX = terrainSummary[summaryX];
					short[][] terrainX = terrain[summaryX];
					summaryX++;
					int summaryY = startSummaryY;
					for( int y=startY; y<=endY; y++ ) {
						int[] surfacesXY = surfacesX[y];
						int[] terrainSummaryXY = terrainSummaryX[summaryY];
						short[] terrainXY = terrainX[summaryY];
						summaryY++;
						int[] result = updateSurfaces(
								temp,
								surfacesXY,
								terrainXY,
								terrainSummaryXY,
								startz, 
								endz, 
								outMaxZ 
						);
						int outMaxZValue = outMaxZ[0];
						if( outMaxZValue > maxBottomZ ) {
							maxBottomZ = outMaxZValue;
						}
						if( minBottomZ < 0 || outMaxZValue < minBottomZ ) {
							minBottomZ = outMaxZValue;
						}
						
						// validate the result (we have bugs)
//						boolean inAir = true;
//						int[] compare = new int[255];
//						int compareIndex = 0;
//						for( int bz=0; bz<world.getBlocksZ(); bz++ ) {
//							Point3D comparePoint = new Point3D( bx, by, bz );
//							byte[][][] compareTerrain = terrainDAO.retrieveObject(comparePoint, null);
//							byte[] compareTerrainXY = compareTerrain[x][y];
//							for( int z = 0; z<world.getBlockDepth(); z++ ) {
//								byte compareTerrainType = compareTerrainXY[z];
//								if( inAir ^ compareTerrainType == 0 ) {
//									inAir = !inAir;
//									compare[compareIndex] = bz * world.getBlockDepth() + z;
//									compareIndex++;
//								}
//							}
//						}
//						if( !inAir ) {
//							compare[compareIndex] = world.getWorldDepth();
//							compareIndex++;
//						}
//						boolean ok;
//						if( compareIndex != result.length ) {
//							ok = false;
//						} else {
//							ok = true;
//							for( int i=0; i<compareIndex; i++ ) {
//								if( compare[i] != result[i] ) {
//									ok = false;
//									break;
//								}
//							}
//						}
//						if( !ok ) {
//							StringBuffer sb = new StringBuffer();
//							sb.append( "startz = " );
//							sb.append( startz );
//							sb.append( "\nendz = " );
//							sb.append( endz );
//							
//							sb.append( "\nterrain {" );
//							for( int i=0; i<terrainXY.length; i++ ) {
//								sb.append( terrainXY[i] );
//								if( i < terrainXY.length-1 ) {
//									sb.append( ',' );
//								}
//							}
//							sb.append( "}\n" );
//
//							sb.append( "summary {" );
//							for( int i=0; i<terrainSummaryXY.length; i++ ) {
//								sb.append( terrainSummaryXY[i] );
//								if( i < terrainSummaryXY.length-1 ) {
//									sb.append( ',' );
//								}
//							}
//							sb.append( "}\n" );
//
//							sb.append( "surface {" );
//							for( int i=0; i<surfacesXY.length; i++ ) {
//								sb.append( surfacesXY[i] );
//								if( i < surfacesXY.length-1 ) {
//									sb.append( ',' );
//								}
//							}
//							sb.append( "}\n" );
//
//							sb.append( "found {" );
//							for( int i=0; i<result.length; i++ ) {
//								sb.append( result[i] );
//								if( i < result.length-1 ) {
//									sb.append( ',' );
//								}
//							}
//							sb.append( "}\n" );
//							sb.append( "expected {" );
//							for( int i=0; i<compareIndex; i++ ) {
//								sb.append( compare[i] );
//								if( i < compareIndex-1 ) {
//									sb.append( ',' );
//								}
//							}
//							sb.append( "}\n" );
//							
//							log.log( Level.WARNING, "invalid comparison\n"+sb );
//							
//							result = new int[compareIndex];
//							System.arraycopy(compare, 0, result, 0, compareIndex);
//						}
						surfacesX[y] = result;
					}
				}
				surfacesDAO.storeObject(new Point(bx, by), surfaces);
			}
		}
		// TODO this value needs to be configured
		int maxUpdateZ = worldZ + terrainUpdate.getDepth();
		maxBottomZ = Math.min( maxUpdateZ + maxShadowDepth, maxBottomZ );
		minBottomZ = Math.max( maxUpdateZ, minBottomZ );

		terrainUpdateResult.setUnderTerrainZ(Math.max( worldZ + terrainUpdate.getDepth(), minBottomZ ), maxBottomZ);
	}


	
	public static final void updateSurfaces(
			int bx, int by, int bz, 
			int startx, int starty, 
			int endx, int endy, 
			int[][][] surfaces, 
			byte[][][] terrain, 
			World world ) {
		int[] temp = new int[ world.getBlockDepth() ];
		int startz = bz * world.getBlockDepth();
		int endz = startz + world.getBlockDepth()-1;
//		System.out.println("bx="+bx+" by="+by+" bz="+bz+" startx="+startx+" starty="+starty+" endx="+endx+" endy="+endy );
		for(int tx=startx; tx<=endx; tx++) {
			int[][] surfacesX = surfaces[tx];
			byte[][] terrainX = terrain[tx];
			for(int ty=starty; ty<=endy; ty++) {
				int[] surfacesXY = surfacesX[ty];
				byte[] terrainXY = terrainX[ty];
				int[] result = updateSurfaces( temp, surfacesXY, terrainXY, startz, endz );
				if( result != null ) {
					surfacesX[ty] = result;
				}
			}
		}
	}
	
	public static final int[] updateSurfaces(
			int[] temp, 
			int[] surfacesXY, 
			short[] terrainXY, 
			int[] summaryXY, 
			int startz, 
			int endz, 
			int[] outMaxZ
	) {
		int[] result;
		int index = 0;
		int fromz = startz;
		int fromIndex = Arrays.binarySearch(surfacesXY, fromz);
		if( fromIndex < 0 ) {
			fromIndex = -(fromIndex + 1);
		}
		int maxz;
		boolean inAir = fromIndex % 2 == 0;
		System.arraycopy(surfacesXY, 0, temp, 0, fromIndex);
		int resultIndex = fromIndex;
		while( index < summaryXY.length ) {
			int toz = fromz + summaryXY[index];
			short terrainType = terrainXY[fromz-startz];
			
			int toIndex = Arrays.binarySearch(surfacesXY, toz);
			if( toIndex < 0 ) {
				toIndex = -(toIndex + 1);
			}
			switch( terrainType ) {
			case (TerrainConstants.TERRAIN_TYPE_AIR | TerrainUpdate.FLAG_FORCE_OVERWRITE):
				if( !inAir ) {
					// end the surface
					temp[resultIndex] = fromz;
					resultIndex++;
				}
				inAir = true;
				break;
			case TerrainUpdate.FLAG_OVERWRITE_IF_AIR:
				if( inAir ^ fromIndex % 2 == 0 ) {
					temp[resultIndex] = fromz;
					resultIndex++;
				} 
				// copy in the remainder
				int length = toIndex - fromIndex;
				if( 
						resultIndex > 0 && 
						temp[resultIndex-1] == surfacesXY[fromIndex] 
				) {
					// overlapping
					resultIndex--;
					fromIndex++;
					length--;
				}

				System.arraycopy(
						surfacesXY, 
						fromIndex, 
						temp, 
						resultIndex, 
						length
				);
				resultIndex += length;
				inAir = resultIndex % 2 == 0;
				break;
			default:
				if( inAir ) {
					// start the surface
					temp[resultIndex] = fromz;
					resultIndex++;
				}
				inAir = false;
			}
			fromz = toz;
			fromIndex = toIndex;
			index++;
		}
		int length = surfacesXY.length - fromIndex;
		if( length > 0 ) {
			if( inAir ^ (fromIndex & 1) == 0 ) {
				temp[resultIndex] = fromz;
				resultIndex++;
				if( inAir ) {
					maxz = fromz;
				} else {
					maxz = -1;
				}
			} else {
				maxz = -1;
			}
			if( 
					resultIndex > 0 && 
					temp[resultIndex-1] == surfacesXY[fromIndex] 
			) {
				// overlapping
				resultIndex--;
				fromIndex++;
				length--;
			} else if( maxz < 0 ){
				maxz = surfacesXY[fromIndex];
			}
			System.arraycopy(
					surfacesXY, 
					fromIndex, 
					temp, 
					resultIndex, 
					length
			);
			resultIndex += length;
		} else {
			// no maxZ (the terrain block is the last)
			maxz = -1;
			if( !inAir ) {
				temp[resultIndex] = endz;
				resultIndex++;
			}
		}
		// TODO : check maxz and its source against the maximum shadow height and reduce if it is greater than that value (efficiency)
		outMaxZ[0] = maxz;
		result = new int[ resultIndex ];
		System.arraycopy(temp, 0, result, 0, resultIndex);
		return result;
	}
	
	
	public static final int[] updateSurfaces(int[] temp, int[] surfacesXY, byte[] terrainXY, int startz, int endz) {
		int tempLength = 0;
		// work out if this pixel starts in air
		int startIndex = Arrays.binarySearch(surfacesXY, startz);
		if( startIndex < 0 ) {
			// normalise 
			startIndex = (-startIndex) - 1;
		}
		int endIndex = Arrays.binarySearch(surfacesXY, endz);
		if( endIndex < 0 ) {
			endIndex = (-endIndex) - 1;
		}
		boolean startingUnderground = startIndex%2 != 0; 
		boolean endUnderground = endIndex % 2 != 0;
		boolean underground = startingUnderground; 
		for( int tz=0; tz<terrainXY.length; tz++ ) {
			byte terrainXYZ = terrainXY[tz];
			if( terrainXYZ == TerrainConstants.TERRAIN_TYPE_AIR ^ !underground ) {
				int z = startz + tz;
				temp[tempLength] = z;
				tempLength++;
				underground = !underground;
			}
		}
		if( underground != endUnderground ) {
			// close it off
			temp[tempLength] = terrainXY.length + startz;
			tempLength++;
		}
		
		// copy the resulting array 
		int[] result;
		if( !ArrayUtils.equals(temp, 0, tempLength, surfacesXY, startIndex, endIndex - startIndex) ) {
			// TODO : make sure the length isn't the same and reuse the surfacesXY
			if( tempLength > 0 ) {
				if( surfacesXY.length > 0 ) {
					int tempStart = 0;//startIndex % 2;
					int tempEnd = tempLength;
//					if( startingUnderground != endUnderground ) {
//						tempEnd -= endIndex % 2;
//					}
					
					result = new int[ surfacesXY.length + tempEnd - tempStart - (endIndex - startIndex) ];
					System.arraycopy(surfacesXY, 0, result, 0, startIndex);
					System.arraycopy(temp, tempStart, result, startIndex, tempEnd - tempStart );
					System.arraycopy(surfacesXY, endIndex, result, startIndex + tempEnd - tempStart, surfacesXY.length - endIndex);
				} else {
					result = new int[ tempLength ];
					System.arraycopy(temp, 0, result, 0, tempLength);
				}
			} else {
				result = surfacesXY;
			}
		} else {
			result = null;
		}
		return result;
	}
	
	private static class UnfinishedPath {
		private WalkablePath path;
		private int tx;
		private int ty;
		private int stepsRemaining;
		private int mintz;
		private int maxtz;
		
		public UnfinishedPath( WalkablePath path, int tx, int ty, int stepsRemaining, int mintz, int maxtz ) {
			this.path = path;
			this.tx = tx;
			this.ty = ty;
			this.stepsRemaining = stepsRemaining;
			this.mintz = mintz;
			this.maxtz = maxtz;
		}
	}
	
	public static final List<WalkablePath> getPaths2(
			int txoff, int tyoff,
			int tx, int ty, int tz, 
			int dx, int dy, 
			int[][][] surfaces,
			int[] xyFromSurfaces,
			int[] xyToSurfaces,
			World world ) {
		int numPoints = world.getGridDiagonal()/2-1; 
		ArrayList<WalkablePath> finishedPaths = new ArrayList<WalkablePath>();
		LinkedList<UnfinishedPath> unfinishedPaths = new LinkedList<UnfinishedPath>();
		ArrayList<Point3D> points = new ArrayList<Point3D>( numPoints );
		points.add( new Point3D( tx+txoff, ty+tyoff, tz ) );
		WalkablePath startPath = new WalkablePath(
				BlockGridTiles.MOVE_TYPE_WALK, 
				points,
				world.getWorldDepth() + SKY_HEIGHT, 
				world.getGridDiagonal()+1, 
				0, 
				0, 
				0, 
				-1, 
				-1
		);
		// find the surface index for this grid tile
		int index = Arrays.binarySearch(xyFromSurfaces, tz);
		int mintz;
		if( index > 0 ) {
			mintz = xyFromSurfaces[index-1];
		} else {
			mintz = -SKY_HEIGHT;
		}
		// should always be an exact match, so we don't need to check for negative values
		unfinishedPaths.add( new UnfinishedPath( startPath, tx, ty, world.getGridDiagonal()/2 - 1, mintz, tz) );
		while( unfinishedPaths.size() > 0 ) {
			UnfinishedPath path = unfinishedPaths.poll();
			boolean valid = true;
			int stepsRemaining = path.stepsRemaining;
			int ntx = path.tx;
			int nty = path.ty;
			int minctz = path.mintz;
			int maxctz = path.maxtz;
			while( stepsRemaining >= 0 ) {
				ntx += dx;
				nty += dy;
				int[] nsurfaces;
				if( stepsRemaining > 0 ) {
					nsurfaces = surfaces[ntx][nty];
				} else {
					nsurfaces = xyToSurfaces;
				}
				stepsRemaining--;
				// work out the overlaps
				boolean first = true;
				int firstx = 0;
				int firsty = 0;
				int firstz = 0;
				int firstminz = 0;
				int firststepup = 0;
				int firstgap = 0;
				for( int i=0; i<nsurfaces.length; i+=2 ) {
					int minnz;
					if( i == 0 ) {
						minnz = -SKY_HEIGHT;
					} else {
						minnz = nsurfaces[ i - 1 ];
					}
					int maxnz = nsurfaces[i];
					if( RangeUtils.overlaps(minnz, maxnz, minctz, maxctz ) ) {
						int gap = Math.min( maxnz, maxctz ) - Math.max( minnz, minctz );
						int stepup = maxnz - maxctz;
						if( first ) {
							firstx = ntx;
							firsty = nty;
							firstz = maxnz;
							firstminz = minnz;
							firstgap = gap;
							firststepup = stepup;
							first = false;
						} else {
							// add in this path as an unfinished path
							WalkablePath clone = new WalkablePath( path.path );
							if( gap < clone.getMinHeight() ) {
								clone.setMinHeight( gap );
							}
							if( stepup > 0 ) {
								if( stepup > clone.getMaxStepUp() ) {
									clone.setMaxStepUp(stepup);
								}
							} else {
								if( -stepup > clone.getMaxStepDown() ) {
									clone.setMaxStepDown(-stepup);
								}
							}
							clone.getPoints().add( new Point3D( ntx+txoff, nty+tyoff, maxnz ) );
							UnfinishedPath unfinishedPath = new UnfinishedPath(
									clone, 
									ntx, 
									nty, 
									stepsRemaining, 
									minnz, maxnz
							);
							unfinishedPaths.add( unfinishedPath );
						}
					}
				}
				// we didn't find one, discard this path, it's a dead end
				if( first ) {
					valid = false;
					break;
				}
				path.path.getPoints().add( new Point3D( firstx+txoff, firsty+tyoff, firstz ) );
				if( firstgap < path.path.getMinHeight() ) {
					path.path.setMinHeight( firstgap );
				}
				if( firststepup > 0 ) {
					if( firststepup > path.path.getMaxStepUp() ) {
						path.path.setMaxStepUp(firststepup);
					}
				} else {
					if( -firststepup > path.path.getMaxStepDown() ) {
						path.path.setMaxStepDown(-firststepup);
					}
				}
				maxctz = firstz;
				minctz = firstminz;
				ntx = firstx;
				nty = firsty;
			}
			if( valid ) {
				finishedPaths.add( path.path );
			}
		}
		return finishedPaths;
	}
	
	public static final List<WalkablePath> getPaths(
			int txoff, int tyoff,
			int tx, int ty, int tz, 
			int dx, int dy, 
			int[][][] surfaces,
			int[] xyFromSurfaces,
			int[] xyToSurfaces,
			World world ) {
		int numPoints = world.getGridDiagonal()/2-1; 
		ArrayList<Point3D> points = new ArrayList<Point3D>( numPoints );
		points.add( new Point3D( tx+txoff, ty+tyoff, tz ) );
		List<WalkablePath> paths = getPaths(
				txoff, tyoff,
				tx, ty, 
				dx, dy, 
				xyFromSurfaces,
				xyToSurfaces,
				0,
				surfaces, 
				numPoints - 1, 
				new WalkablePath(
						BlockGridTiles.MOVE_TYPE_WALK, 
						points,
						world.getWorldDepth() + SKY_HEIGHT, 
						world.getGridDiagonal()+1, 
						0, 
						0, 
						0, 
						-1, 
						-1
				)
		);
		return paths;
	}
	
	public static final List<WalkablePath> getPaths( 
			int txoff, int tyoff,
			int tx, int ty, 
			int dx, int dy, 
			int[] osurfaces,
			int[] dsurfaces,
			int oSurfaceId, 
			int[][][] surfaces, 
			int stepsRemaining, 
			WalkablePath path
	) {
		int ntx = tx + dx;
		int nty = ty + dy;
//		System.out.println( "("+ntx+","+nty+") "+stepsRemaining );
		int[] nsurfaces;
		if( stepsRemaining > 0 ) {
			nsurfaces = surfaces[ntx][nty];
		} else {
			nsurfaces = dsurfaces;
		}
		// work out if it's connected
		int minotz;
		if( oSurfaceId > 0 ) {
			minotz = osurfaces[ oSurfaceId-1 ];
		} else {
			minotz = -SKY_HEIGHT;
		}
		int maxotz = osurfaces[ oSurfaceId ];
		int[] overlappingSurfaceIndexes = new int[nsurfaces.length/2 + nsurfaces.length%2];
		int overlappingSurfacesCount = 0;
		// could do a binary search to find the start, but would probably actually be slower
		for( int i=0; i<nsurfaces.length; i+=2 ) {
			int minntz;
			if( i > 0 ) {
				minntz = nsurfaces[i-1];
			} else {
				minntz = -SKY_HEIGHT;
			}
			int maxntz = nsurfaces[i];
			
			if( RangeUtils.overlaps(minotz, maxotz, minntz, maxntz) ) {
				overlappingSurfaceIndexes[ overlappingSurfacesCount ] = i;
				overlappingSurfacesCount++;
			}
		}
		ArrayList<WalkablePath> result;
		result = new ArrayList<WalkablePath>( overlappingSurfacesCount );
		for( int i=overlappingSurfacesCount; i>0; ) {
			i--;
			WalkablePath npath;
			if( overlappingSurfacesCount == 0 ) {
				npath = path;
			} else {
				npath = new WalkablePath( path );
			}
			// there is one surface, continue
			int nsurfaceIndex = overlappingSurfaceIndexes[i];
			int maxntz = nsurfaces[nsurfaceIndex];
			int minntz;
			if( nsurfaceIndex > 0 ) {
				minntz = nsurfaces[nsurfaceIndex-1];
			} else {
				minntz = -SKY_HEIGHT;
			}
			npath.getPoints().add( new Point3D(txoff+ntx, tyoff+nty, maxntz ) );
			int gap = Math.min( maxotz, maxntz ) - Math.max( minotz, minntz );
			if( gap < npath.getMinHeight() ) {
				npath.setMinHeight( gap );
			}
			int stepup = maxntz - maxotz;
			if( stepup > 0 ) {
				if( stepup > npath.getMaxStepUp() ) {
					npath.setMaxStepUp(stepup);
				}
			} else {
				if( -stepup > npath.getMaxStepDown() ) {
					npath.setMaxStepDown(-stepup);
				}
			}
			if( stepsRemaining > 0 ) {
				 List<WalkablePath> subpaths = getPaths(
						txoff, tyoff,
						ntx, nty,  
						dx, dy, 
						nsurfaces, 
						dsurfaces,
						nsurfaceIndex,
						surfaces, 
						stepsRemaining-1, 
						npath
				);
				result.addAll( subpaths );
			} else {
				result.add( npath );
			}
		}
		return result;
	}
	
//	public static final int getTx( int gx, int gy, World world ) {
//		if( gy % 2 == 0 ) {
//			return gx * world.getGridDiagonal() + world.getGridDiagonal() / 2;
//		} else {
//			return gx * world.getGridDiagonal();
//		}
//	}
//	
//	public static final int getTy( int gx, int gy, World world ) {
//		return gy * world.getGridDiagonal() / 2;
//	}
	
	public static final int getTx( int gx, int gy, RotatedWorld world ) {
		return getTx( gx, gy, world.getOriginalWorld() );
	}
	
	public static final int getTx( int gx, int gy, World world ) {
		if( (gy & 1) == 0 ) {
			return (gx << world.getGridDiagonalShift()) + (world.getGridDiagonal() >> 1);
		} else {
			return gx << world.getGridDiagonalShift();
		}
	}
	
	public static final int getTy( int gx, int gy, RotatedWorld world ) {
		return getTy( gx, gy, world.getOriginalWorld() );
	}
	
	public static final int getTy( int gx, int gy, World world ) {
		return gy << (world.getGridDiagonalShift()-1);
	}
	
	public static final Point getGridCoordinates( int gx, int gy, int direction, Point p ) {
		switch( direction ) {
		case BlockGridTiles.INDEX_NE:
			if( (gy & 1) == 0 ) {
				p.x = gx + 1;
				p.y = gy - 1;
			} else {
				p.x = gx;
				p.y = gy - 1;
			}
			break;
		case BlockGridTiles.INDEX_SE:
			if( (gy & 1) == 0 ) {
				p.x = gx + 1;
				p.y = gy + 1;
			} else {
				p.x = gx;
				p.y = gy + 1;
			}
			break;
		case BlockGridTiles.INDEX_SW:
			if( (gy & 1) == 0 ) {
				p.x = gx;
				p.y = gy + 1;
			} else {
				p.x = gx - 1;
				p.y = gy + 1;
			}
			break;
		case BlockGridTiles.INDEX_NW:
			if( (gy & 1) == 0 ) {
				p.x = gx;
				p.y = gy - 1;
			} else {
				p.x = gx - 1;
				p.y = gy - 1;
			}
			break;
		}
		return p;
	}
	
	public static final Point getPathCoordinates( int gx, int gy, int direction, Point result ) {
		switch( direction ) {
		case BlockGridTiles.INDEX_NE:
			if( gy % 2 == 0 ) {
				result.x = gx * 2 + 1;
				result.y = gy - 1;
			} else {
				result.x = gx * 2;
				result.y = gy - 1;
			}
			break;
		case BlockGridTiles.INDEX_SE:
			if( gy % 2 == 0 ) {
				result.x = gx * 2 + 1;
				result.y = gy;
			} else {
				result.x = gx * 2;
				result.y = gy;
			}
			break;
		case BlockGridTiles.INDEX_SW:
			if( gy % 2 == 0 ) {
				result.x = gx * 2;
				result.y = gy;
			} else {
				result.x = gx * 2 - 1;
				result.y = gy;
			}
			break;
		case BlockGridTiles.INDEX_NW:
			if( gy % 2 == 0 ) {
				result.x = gx * 2;
				result.y = gy - 1;
			} else {
				result.x = gx * 2 - 1;
				result.y = gy - 1;
			}
			break;
		}
		return result;
	}
	
	public static final void updateSurfaces(
			int wx, int wy, int ww, int wh, 
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO,
			byte[][][] terrain, 
			World world
	) {
		int startBlockX = wx / world.getBlockWidth();
		int startBlockY = wy / world.getBlockHeight();
		int endBlockX = (wx + ww) / world.getBlockWidth();
		int endBlockY = (wy + wh) / world.getBlockHeight();
		int startX = wx % world.getBlockWidth();
		int startY = wy % world.getBlockHeight();
		int endX = (wx + ww) % world.getBlockWidth();
		int endY = (wy + wh) % world.getBlockHeight();
		if( endX > 0 ) {
			endBlockX ++;
		}
		if( endY > 0 ) {
			endBlockY ++;
		}
		for( int bx = startBlockX; bx <= endBlockX; bx++ ) {
			int x;
			if( bx == startBlockX ) {
				x = startX;
			} else {
				x = 0;
			}
			int w;
			if( bx == endBlockX ) {
				w = endX - x; 
			} else {
				w = world.getBlockWidth() - x; 
			}
			if( bx == endBlockX)
			for( int by = startBlockY; by <= endBlockY; by++ ) {
				int y;
				if( by == startBlockY ) {
					y = startY;
				} else {
					y = 0;
				}
				int h;
				if( by == endBlockY ) {
					h = endY - y;
				} else {
					h = world.getBlockHeight() - y;
				}
				Point b = new Point( bx, by );
				int[][][] surfaces = surfacesDAO.retrieveObject(b);
				
				int[][] copy = new int[h][0];
				
				// wipe the changed blocks
				for( int sx = x+w; sx>x; ) {
					sx--;
					System.arraycopy( copy, 0, surfaces[x], y, h );
				}
				
				System.out.println("["+bx+','+by+','+x+','+y+','+w+','+h+']');
				
				deriveSurfaces(
						bx, by, 
						x, y, 
						x+w-1, y+h-1, 
						surfaces, 
						terrain, 
						terrainDAO, 
						world
				);
			}
		}
	}
	
	public static final void regenerateSurfaces( 
			int bx, int by, int bw, int bh, 
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point3D, Pointer<byte[][][]>> terrainDAO,
			byte[][][] terrain,
			World world
	) {
		for( int x=bx+bw; x>bx; ) {
			x--;
			for( int y=by+bh; y>by; ) {
				y--;
				Point p = new Point( x, y );
				int[][][] surfaces = new int[ world.getBlockWidth() ][ world.getBlockHeight() ][0];
				deriveSurfaces(
						x, y, 
						0, 0, 
						world.getBlockWidth()-1, 
						world.getBlockHeight()-1,
						surfaces, 
						terrain, 
						terrainDAO, 
						world
				);
				surfacesDAO.storeObject(p, surfaces);
			}
		}
	}
	
	public static final void regenerateGridTiles(
			int bx, int by, int bw, int bh, 
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point, BlockGridTiles> gridTilesDAO, 
			World world
	){
		int gridsX = world.getXGridTilesPerBlock();
		int gridsY = world.getYGridTilesPerBlock();
		for( int x=bx+bw; x>bx; ) {
			x--;
			for( int y=by+bh; y>by; ) {
				y--;
				Point p = new Point( x, y );
				GridTile[][][] gridTiles = new GridTile[gridsX][gridsY][];
				findGridTiles(0, 0, gridsX-1, gridsY-1, surfacesDAO.retrieveObject(p), gridTiles, world);
				BlockGridTiles blockGridTiles = new BlockGridTiles( x, y, gridTiles, null );
				gridTilesDAO.storeObject(p, blockGridTiles);
			}
		}
		for( int x=bx+bw; x>bx; ) {
			x--;
			for( int y=by+bh; y>by; ) {
				y--;
				Point p = new Point( x, y );
				mapPaths(
						p, 
						0, 0, world.getXPathTilesPerBlock()-1, world.getYPathTilesPerBlock()-1,
						surfacesDAO, 
						gridTilesDAO, 
						world
				);
			}
		}
	}
	
	public static final void updateGridTiles( 
			int startPathX, int startPathY, int endPathX, int endPathY,
			int startEPathX, int startEPathY, int endEPathX, int endEPathY,			
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point, BlockGridTiles> gridTilesDAO,
			World world
	) {
		// TODO use shift instead of divide
		int xPathTilesPerBlock = world.getXPathTilesPerBlock();
		int yPathTilesPerBlock = world.getYPathTilesPerBlock();
		int startbx = startPathX / xPathTilesPerBlock;
		int startby = startPathY / yPathTilesPerBlock;
		int endbx = endPathX / xPathTilesPerBlock;
		int endby = endPathY / yPathTilesPerBlock;
		
		for( int bx = startbx; bx<=endbx; bx++ ) {
			int startpx;
			int endpx;
			if( bx == startbx ) {
				startpx = startPathX % xPathTilesPerBlock;
			} else {
				startpx = 0;
			}
			if( bx == endbx ) {
				endpx = endPathX % xPathTilesPerBlock;
			} else {
				endpx = xPathTilesPerBlock - 1;
			}
			for( int by = startby; by<=endby; by++ ) {
				int startpy;
				int endpy;
				if( by == startby ) {
					startpy = startPathY % yPathTilesPerBlock;
				} else {
					startpy = 0;
				}
				if( by == endby ) {
					endpy = endPathY % yPathTilesPerBlock;
				} else {
					endpy = yPathTilesPerBlock - 1;
				}
				// regenerate the grid tiles
				Point p = new Point( bx, by );
				BlockGridTiles blockGridTiles = gridTilesDAO.retrieveObject(p);
				findGridTilesByPath(
						startpx, startpy, endpx, endpy,
						surfacesDAO.retrieveObject(p), 
						blockGridTiles.getGridTiles(), 
						world
				);
				gridTilesDAO.storeObject(p, blockGridTiles);
			}
		}
		
		// redo external paths and grid tile indexes
		int startebx = startEPathX / xPathTilesPerBlock;
		int starteby = startEPathY / yPathTilesPerBlock;
		int endebx = endEPathX / xPathTilesPerBlock;
		int endeby = endEPathY / yPathTilesPerBlock;

		for( int bx = startebx; bx<=endebx; bx++ ) {
			int startpx;
			int endpx;
			if( bx == startebx ) {
				startpx = startEPathX % xPathTilesPerBlock;
			} else {
				startpx = 0;
			}
			if( bx == endebx ) {
				endpx = endEPathX % xPathTilesPerBlock;
			} else {
				endpx = xPathTilesPerBlock - 1;
			}
			for( int by = starteby; by<=endeby; by++ ) {
				int startpy;
				int endpy;
				if( by == starteby ) {
					startpy = startEPathY % yPathTilesPerBlock;
				} else {
					startpy = 0;
				}
				if( by == endeby ) {
					endpy = endEPathY % yPathTilesPerBlock;
				} else {
					endpy = yPathTilesPerBlock - 1;
				}
				// regenerate the paths
				Point p = new Point( bx, by );
				mapPaths(
						p,
						startpx, startpy, endpx, endpy,						
						surfacesDAO, 
						gridTilesDAO, 
						world
				);
			}
		}

		// regenerate the paths
//		for( int x=startbx; x<=endbx; x++) {
//			for( int y=startby; y<=endby; y++ ) {
//				Point p = new Point( x, y );
//				mapPaths(
//						p,
//						0, 0, world.getXPathTilesPerBlock()-1, world.getYPathTilesPerBlock()-1,						
//						surfacesDAO, 
//						gridTilesDAO, 
//						world
//				);
//			}
//		}
	}
	
	public static final void findGridTilesByPath(
			int startpx, int startpy, int endpx, int endpy,
			int[][][] surfaces, 
			GridTile[][][] tiles, 
			World world
	) {
		for( int x = startpx; x<=endpx; x++ ) {
			for( int y = startpy; y<=endpy; y++ ) {
				// only interested in \ diagonals 
				if( (x+y) % 2 != 0 ) {
					// gx from
					// gy from
					int gx = x / 2;
					int gy = y;
					
					int tx = TerrainUtils.getTx(gx, gy, world);
					int ty = TerrainUtils.getTy(gx, gy, world);
					int[] surface = surfaces[tx][ty];
					GridTile[] surfaceTiles = new GridTile[ surface.length / 2 + surface.length % 2 ];
					for( int i=0; i<surface.length; i+=2 ) {
						int tz = surface[i];
						GridTile gridTile = new GridTile( 
								tz
						);
						surfaceTiles[ i/2 ] = gridTile;
					}
					tiles[gx][gy] = surfaceTiles;
				}
			}
		}
	}
	
	public static final void findGridTiles(
			int gxstart, int gystart, int gxend, int gyend, 
			int[][][] surfaces,
			GridTile[][][] tiles,
			World world ) {

		for( int x = gxstart; x<=gxend; x++ ) {
			for( int y = gystart; y<=gyend; y++ ) {
				int tx = TerrainUtils.getTx(x, y, world);
				int ty = TerrainUtils.getTy(x, y, world);
				int[] surface = surfaces[tx][ty];
				GridTile[] surfaceTiles = new GridTile[ surface.length / 2 + surface.length % 2 ];
				for( int i=0; i<surface.length; i+=2 ) {
					int tz = surface[i];
					GridTile gridTile = new GridTile( 
							tz
					);
					surfaceTiles[ i/2 ] = gridTile;
				}
				tiles[x][y] = surfaceTiles;
			}
		}
	}

	public static final void mapPaths(
			Point b, 
			int startpx, int startpy, int endpx, int endpy,
			ObjectDAO<Point, int[][][]> surfacesDAO, 
			ObjectDAO<Point, BlockGridTiles> gridTileDAO,
			World world
	) {
		int bx = b.x;
		int by = b.y;
		int[][][] surfaces = surfacesDAO.retrieveObject(b);
		int txoff = bx * world.getBlockWidth();
		int tyoff = by * world.getBlockHeight();
		int gridsX = world.getXGridTilesPerBlock();
		int gridsY = world.getYGridTilesPerBlock();
		int pathsX = world.getXPathTilesPerBlock();
		int pathsY = world.getYPathTilesPerBlock();
		WalkablePath[][][] paths;
		BlockGridTiles gridTiles = gridTileDAO.retrieveObject(b);
		paths = gridTiles.getPaths();
		if( paths == null ) {
			paths = new WalkablePath[pathsX][pathsY][];
		}
		ArrayList<WalkablePath> allPaths = new ArrayList<WalkablePath>();
		
		int[][][] southSurfaces;
		BlockGridTiles southGridTiles;
		if( by+1 < world.getBlocksY() ) {
			Point b1 = new Point( bx, by+1 );
			southSurfaces = surfacesDAO.retrieveObject( b1 );
			southGridTiles = gridTileDAO.retrieveObject( b1 );
		} else {
			southSurfaces = null;
			southGridTiles = null;
		}
		int[][][] eastSurfaces;
		BlockGridTiles eastGridTiles;
		if( bx + 1 < world.getBlocksX() ) {
			Point b1 = new Point( bx+1, by );
			eastSurfaces = surfacesDAO.retrieveObject( b1 );
			eastGridTiles = gridTileDAO.retrieveObject( b1 );
		} else {
			eastSurfaces = null;
			eastGridTiles = null;
		}
		for( int px=startpx; px<=endpx; px++ ) {
			for( int py=startpy; py<=endpy; py++ ) {
				
				int dx;
				int dy;
				
				int gxfrom;
				int gyfrom;
				int gxto;
				int gyto;
				if( py % 2 == 0 ) {
					if( px % 2 == 0 ) {
						gxfrom = px/2;
						gyfrom = py + 1;
						gxto = px/2;
						gyto = py;
						dx = 1;
						dy = -1;
					} else {
						gxfrom = px/2;
						gyfrom = py;
						gxto = (px+1)/2;
						gyto = py+1;						
						dx = 1;
						dy = 1;
					}
				} else {
					if( px % 2 == 0 ) {
						gxfrom = px/2;
						gyfrom = py;
						gxto = px/2;
						gyto = py+1;
						dx = 1;
						dy = 1;
					} else {
						gxfrom = px/2;
						gyfrom = py+1;
						gxto = (px+1)/2;
						gyto = py;												
						dx = 1;
						dy = -1;
					}
				}
				allPaths.clear();
				GridTile[] fromTiles;
				GridTile[] toTiles;
				int[] gxyfromSurfaces;
				int[] gxytoSurfaces;
				int txfrom = TerrainUtils.getTx(gxfrom, gyfrom, world);
				int tyfrom = TerrainUtils.getTy(gxfrom, gyfrom, world);
				int txto = TerrainUtils.getTx(gxto, gyto, world);
				int tyto = TerrainUtils.getTy(gxto, gyto, world);
				//System.out.println( "("+px+","+py+") ("+gxfrom+","+gyfrom+"->"+gxto+","+gyto+")/("+gridsX+","+gridsY+") ("+txfrom+","+tyfrom+")/("+world.getBlockWidth()+","+world.getBlockHeight()+")" );
				if( by == 0 && (gyfrom == 0 || gyto == 0)  || bx == 0 && gxfrom == 0 && gyfrom % 2 != 0 ) {
					fromTiles = null;
					gxyfromSurfaces = null;					
				} else if( gyfrom < gridsY ) {
					fromTiles = gridTiles.getGridTiles(gxfrom, gyfrom);
					gxyfromSurfaces = surfaces[txfrom][tyfrom];
				} else if( southGridTiles != null ){
					fromTiles = southGridTiles.getGridTiles(gxfrom, gyfrom % gridsY);
					gxyfromSurfaces = southSurfaces[txfrom][tyfrom%world.getBlockHeight()];
				} else {
					fromTiles = null;
					gxyfromSurfaces = null;
				}
				if( gyto < gridsY && gxto < gridsX ) {
					gxytoSurfaces = surfaces[txto][tyto];
					toTiles = gridTiles.getGridTiles(gxto, gyto);
				} else if( gxto < gridsX ) {
					if( southSurfaces != null ) {
						gxytoSurfaces = southSurfaces[txto][tyto%world.getBlockHeight()];
						toTiles = southGridTiles.getGridTiles(gxto, gyto%gridsY);
					} else {
						gxytoSurfaces = null;
						toTiles = null;
					}
				} else {
					if( eastSurfaces != null ) { 
						gxytoSurfaces = eastSurfaces[txto%world.getBlockWidth()][tyto];
						toTiles = eastGridTiles.getGridTiles( gxto%gridsX, gyto);
					} else {
						gxytoSurfaces = null;
						toTiles = null;
					}
				}
				if( gxyfromSurfaces != null && gxytoSurfaces != null ) {
					allPaths.ensureCapacity( fromTiles.length );
					for( int i=fromTiles.length; i>0; ) {
						i--;
						GridTile fromTile = fromTiles[i];
						List<WalkablePath> gridPaths;
						gridPaths = TerrainUtils.getPaths2(
								txoff, tyoff,
								txfrom, tyfrom, fromTile.getZ(), 
								dx, dy, 
								surfaces,
								gxyfromSurfaces,
								gxytoSurfaces,
								world
						);
						allPaths.addAll( gridPaths );
					}
					if( allPaths.size() > 1 ) {
						log.log( Level.INFO, "got a "+allPaths.size()+" paths at ("+px+","+py+")");
					}
				}
				paths[px][py] = allPaths.toArray(new WalkablePath[ allPaths.size() ]);
			}
		}
		// link up indices for paths
		int[] tempPaths = new int[MAX_PATHS];
		for( int px=startpx; px<=endpx; px++ ) {
			for( int py=startpy; py<=endpy; py++ ) {
				int gxfrom;
				int gyfrom;
				int gxto;
				int gyto;
				int direction;
				if( py % 2 == 0 ) {
					if( px % 2 == 0 ) {
						gxfrom = px/2;
						gyfrom = py + 1;
						gxto = px/2;
						gyto = py;
						direction = BlockGridTiles.INDEX_NE;
					} else {
						gxfrom = px/2;
						gyfrom = py;
						gxto = (px+1)/2;
						gyto = py+1;						
						direction = BlockGridTiles.INDEX_SE;
					}
				} else {
					if( px % 2 == 0 ) {
						gxfrom = px/2;
						gyfrom = py;
						gxto = px/2;
						gyto = py+1;
						direction = BlockGridTiles.INDEX_SE;
					} else {
						gxfrom = px/2;
						gyfrom = py+1;
						gxto = (px+1)/2;
						gyto = py;												
						direction = BlockGridTiles.INDEX_NE;
					}
				}
				GridTile[] fromTiles;
				if( gxfrom >= gridsX ) {
					if( eastGridTiles != null ) {
						fromTiles = eastGridTiles.getGridTiles( gxfrom%gridsX, gyfrom );
					} else {
						fromTiles = null;
					}
				} else if( gyfrom >= gridsY ) {
					if( southGridTiles != null ) {
						fromTiles = southGridTiles.getGridTiles( gxfrom, gyfrom%gridsY );
					} else {
						fromTiles = null;
					}
				} else {
					fromTiles = gridTiles.getGridTiles( gxfrom, gyfrom );
				}
				GridTile[] toTiles;
				if( gxto >= gridsX ) {
					if( eastGridTiles != null ) {
						toTiles = eastGridTiles.getGridTiles( gxto%gridsX, gyto );
					} else {
						toTiles = null;
					}
				} else if( gyto >= gridsY ) {
					if( southGridTiles != null ) {
						toTiles = southGridTiles.getGridTiles( gxto, gyto%gridsY );
					} else { 
						toTiles = null;
					}
				} else {
					toTiles = gridTiles.getGridTiles( gxto, gyto );
				}
				WalkablePath[] gridPaths = paths[px][py];
				if( fromTiles != null ) {
					//int pathIndex = 0;
					for( int i=0; i<fromTiles.length; i++ ) {
						GridTile fromTile = fromTiles[i];
						int tz = fromTile.getZ();
						int tempPathsCount = 0;
//						while( pathIndex < gridPaths.length ) {
//							WalkablePath path = gridPaths[pathIndex];
//							int pz = path.getPoints().get(0).getZ(); 
//							if( pz == tz ) {
//								tempPaths[tempPathsCount] = pathIndex;
//								tempPathsCount++;
//								path.setFromGridIndex( i );
//								pathIndex++;
//							} else if( pz < tz ) {
//								pathIndex++;
//							} else {
//								break;
//							}
//						}
						int pathFromIndex = -1;
						for( int j=0; j<gridPaths.length; j++ ) {
							WalkablePath path = gridPaths[j];
							int pz = path.getPoints().get( 0 ).getZ();
							if( pz == tz ) {
								tempPaths[tempPathsCount]=j;
								tempPathsCount++;
								pathFromIndex = i;
								path.setFromGridIndex( pathFromIndex );
								//break;
							}
						}
						if( pathFromIndex < 0 ) {
							log.info( "could not match from tile ("+bx+","+by+") ("+gxfrom+","+gyfrom+")" );
						}
						int[] pathIndexes = new int[tempPathsCount];
						System.arraycopy(tempPaths, 0, pathIndexes, 0, tempPathsCount);
						fromTile.getPathIndexes()[direction] = pathIndexes;
					} 
				}

				if( toTiles != null ) {
					int otherDirection = (direction + 2) % 4;
					for( int i=0; i<toTiles.length; i++ ) {
						GridTile toTile = toTiles[i];
						int tz = toTile.getZ();
						int tempPathsCount = 0;
//						while( pathIndex < gridPaths.length ) {
//							WalkablePath path = gridPaths[pathIndex];
//							List<Point3D> points = path.getPoints(); 
//							int pz = points.get(points.size()-1).getZ(); 
//							if( pz == tz ) {
//								tempPaths[tempPathsCount] = pathIndex;
//								tempPathsCount++;
//								path.setToGridIndex( i );
//								pathIndex++;
//							} else if( pz < tz ) {
//								pathIndex++;
//							} else {
//								break;
//							}
//						}
						int pathToIndex = -1;
						for( int j=0; j<gridPaths.length; j++ ) {
							WalkablePath path = gridPaths[j];
							List<Point3D> points = path.getPoints(); 
							int pz = points.get(points.size()-1).getZ(); 
							if( pz == tz ) {
								tempPaths[tempPathsCount] = j;
								tempPathsCount++;
								pathToIndex = i;
								path.setToGridIndex( pathToIndex );
							}
						}
						if( pathToIndex < 0 ) {
							log.info( "could not match to tile ("+bx+","+by+") ("+gxto+","+gyto+")" );
						}
						int[] pathIndexes = new int[tempPathsCount];
						System.arraycopy(tempPaths, 0, pathIndexes, 0, tempPathsCount);
						toTile.getPathIndexes()[otherDirection] = pathIndexes;
					}
				}
			}
		}
		
		gridTiles.setPaths( paths );
		gridTileDAO.storeObject(b, gridTiles);
		if( southGridTiles != null ) {
			Point b1 = new Point( bx, by+1 );
			gridTileDAO.storeObject(b1, southGridTiles);
		}
		if( eastGridTiles != null ) {
			Point b1 = new Point( bx+1, by );
			gridTileDAO.storeObject(b1, eastGridTiles);
		}
//		System.out.println("("+bx+","+by+")");
//		for( int x=0; x<paths.length; x++ ) {
//			for( int y=0; y<paths[x].length; y++ ) {
//				System.out.print(paths[x][y].length);
//				System.out.print(' ');
//			}
//			System.out.println();
//		}
	}	
}
